#二分查找
# 参数说明：
# arr: 有序数组
# x: 要查找的目标值
# 返回值：如果找到目标值返回其索引，否则返回-1
def binary_search(arr,x):
    # 初始化左右指针
    l = 0               # 左边界指针
    r = len(arr)-1      # 右边界指针
    while l <= r:       # 当左指针小于等于右指针时继续查找
        mid = l + (r - l) // 2  # 计算中间位置（使用这种方式计算可以防止溢出）
        if arr[mid] == x:       # 找到目标值
            return mid
        elif arr[mid] < x:      # 目标值在右半部分
            l = mid + 1         # 左指针移动到中间位置的右边
        else:                   # 目标值在左半部分
            r = mid -1          # 右指针移动到中间位置的左边
    return -1                   # 没有找到目标值
arr1 = [1,2,3,4,5,6,7,8,9,10]
x = 6
print(binary_search(arr1,x))

'''

'''

#希尔排序
# 参数说明：
# arr: 待排序的数组
# 返回值：排序后的数组
def shell_sort(arr):        
    n = len(arr)              # 获取数组长度
    gap = n // 2              # 初始化间隔（gap）为长度的一半
    # 对每个间隔的元素进行插入排序
    while gap > 0:            # 当间隔大于0时继续排序
        for i in range(gap,n):    # 从gap开始遍历数组
            temp = arr[i]         # 保存当前元素
            j = i
            # 对间隔为gap的元素进行插入排序
            while j >= gap and arr[j-gap] > temp:
                arr[j] = arr[j-gap]   # 将较大的元素向后移动
                j -= gap              # 向前移动gap个位置
            arr[j] = temp            # 将当前元素插入到正确位置
        gap //= 2                    # 将间隔缩小一半
    return arr
arr2 = [64, 34, 25, 12, 22, 11, 90]
print(shell_sort(arr2))
#桶排序
# 参数说明：
# arr: 待排序的数组
# 返回值：排序后的数组
def bucket_sort(arr):
    # 创建桶（这里创建了与原数组等长的桶）
    bucket = []
    for i in range(len(arr)):
        bucket.append([])   #初始化空桶
    # 将元素分配到对应的桶中
    for j in arr:
        index_b = int(10 * j)  #计算元素应该放入的桶的索引
        bucket[index_b].append(j)  #将元素放入对应的桶中
    # 对每个桶中的元素进行排序
    for i in range(len(arr)):
        bucket[i] = sorted(bucket[i])#使用python内置的sorted函数对每个桶中的元素进行排序
    # 将排序后的元素重新放回原数组
    k = 0                     # 初始化索引k
    for i in range(len(arr)):  #遍历每个桶
        for j in range(len(bucket[i])):  #遍历每个桶中的元素
            arr[k] = bucket[i][j]        #将排序后的元素放回原数组
            k += 1
    return arr
arr3 = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
print(bucket_sort(arr3))
#基数排序算法实现
# 基数排序的辅助函数：按照数字的某一位进行计数排序
# 参数说明：
# arr: 待排序的数组
# exp1: 当前处理的位数（1代表个位，10代表十位，100代表百位...）
# 返回值：无，直接修改原数组
def counting_sort_exp(arr,exp1) :
    n = len(arr)                    #获取数组长度
    output = [0] * n               #创建输出数组
    count = [0] * 10               #创建计数数组，0-9共10个数字
    
    #统计当前位数上每个数字出现的次数
    for i in range(0,n) :
        index = arr[i] // exp1      #获取当前位上的数字
        count[index % 10] += 1      #对应计数加1
    
    #计算累计计数，使count[i]包含位数<=i的元素个数
    for i in range(1,10):
        count[i] += count[i-1]
        
    #从后向前遍历，保持排序的稳定性
    i = n - 1
    while i >= 0 :
        index = arr[i] // exp1
        output[count[index % 10] - 1] = arr[i] #将元素放入正确位置
        count[index % 10] -= 1                  #计数减1
        i -= 1
        
    #将排序后的结果复制回原数组
    for i in range(0,len(arr)) :
        arr[i] = output[i]

# 基数排序主函数
# 参数说明：
# arr: 待排序的非负整数数组
# 返回值：排序后的数组
def radix_sort(arr) :
    max1 = max(arr)                      #获取数组中的最大值
    exp = 1                              #初始化当前处理的位数为1（个位）
    
    # 按照个位、十位、百位...依次进行计数排序
    while max1 // exp > 0 :
        counting_sort_exp(arr,exp)       #对当前位进行计数排序
        exp *= 10                        #处理下一个位数
    return arr

# 测试基数排序
arr4 = [170,45,90,800,24,2,66]
print("原始数组：", arr4)
print("排序结果：", radix_sort(arr4.copy()))   #测试基数排序
